#include <stdio.h>

#define M 16
#define INF 65535

int num = 0;
int graph[M][M];
int dis[M][M];
int path[M][M];

void input() {
    int i, j;
    scanf("%d", &num);
    for (i = 0; i < num; i++) {
        for (j = 0; j < num; j++) {
            scanf("%d", &graph[i][j]);
            if (graph[i][j] == 0) {
                graph[i][j] = INF;
            }
        }
    }
}

void test_input() {
    int i, j;
    num = 9;
    for (i = 0; i < num; i++)/* 初始化图 */
       {
           for ( j = 0; j < num; j++)
           {
               if (i==j) {
                   graph[i][j]=0;
               }
               else {
                   graph[i][j] = INF;
                   graph[j][i] = INF;
               }
           }
       }
       graph[0][1]=1;
       graph[0][2]=5;
       graph[1][2]=3;
       graph[1][3]=7;
       graph[1][4]=5;
       graph[2][4]=1;
       graph[2][5]=7;
       graph[3][4]=2;
       graph[3][6]=3;
       graph[4][5]=3;
       graph[4][6]=6;
       graph[4][7]=9;
       graph[5][7]=5;
       graph[6][7]=2;
       graph[6][8]=7;
       graph[7][8]=4;
       for(i = 0; i < num; i++)
       {
           for(j = i; j < num; j++)
           {
               graph[j][i] = graph[i][j];
           }
       }
}

void init() {
    int i, j;
    for (i = 0; i < num; i++) {
        for (j = 0; j < num; j++) {
            path[i][j] = j;
            dis[i][j] = graph[i][j];
        }
    }
}


void floyd() {
    int i, j, k;
    init();
    for (k = 0; k < num; k++) {
        for (i = 0; i < num; i++) {
            for (j = 0; j < num; j++) {
                if (dis[i][k] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    path[i][j] = path[i][k];
                    //[i][k] #[k][i] [k][j]
                }
            }
        }
    }
}


void output() {
    int i, j,  k;
    for (i = 0; i < num; i++) {
        for (j = i + 1; j < num; j++) {
            printf("%d -> %d: ", i, j);
            k = path[i][j];
            printf("%d-", i);
            while (k != j) {
                printf("%d-", k);
                k = path[k][j];
            }
            printf("%d", j);
            printf(" distance:%d\n", dis[i][j]);
        }
    }
}

void test() {
    test_input();
    floyd();
    output();
}

int main(void)
{
    test();
    input();
    floyd();
    output();
    return 0;
}

